class Solution
{
    int ret, path, aim;
public:
    int findTargetSumWays(vector<int>& nums, int target)
    {
        aim = target;
        dfs(nums, 0);
        return ret;
    }

    void dfs(vector<int>& nums, int pos)
    {
        if (pos == nums.size())
        {
            if (path == aim) ret++;
            return;
        }

        path += nums[pos];
        dfs(nums, pos + 1);
        path -= nums[pos];

        path -= nums[pos];
        dfs(nums, pos + 1);
        path += nums[pos];
    }
};


class Solution
{
    int ret, aim;
public:
    int findTargetSumWays(vector<int>& nums, int target)
    {
        aim = target;
        dfs(nums, 0, 0);
        return ret;
    }

    void dfs(vector<int>& nums, int pos, int path)
    {
        if (pos == nums.size())
        {
            if (path == aim) ret++;
            return;
        }

        dfs(nums, pos + 1, path + nums[pos]);

        dfs(nums, pos + 1, path - nums[pos]);
    }
};